#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<queue>

using namespace std;

class Solution {
public:
    int dx[4] = { -1,1,0,0 };
    int dy[4] = { 0,0,1,-1 };

    int dfs(vector<vector<int>>& grid, int x, int y)
    {
        int m = grid.size(), n = grid[0].size();
        if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] == 0)
        {
            return 0;
        }

        int count = 1;
        grid[x][y] = 0;
        for (int i = 0; i < 4; i++)
        {
            count += dfs(grid, x + dx[i], y + dy[i]);
        }
        return count;
    }

    int bfs(vector<vector<int>>& grid, int x, int y)
    {
        int m = grid.size(), n = grid[0].size();
        int ans = 0;
        queue<pair<int, int>> q;
        q.push({ x,y });
        while (!q.empty())
        {
            int i = q.front().first;
            int j = q.front().second;
            q.pop();
            if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == 0)
            {
                continue;
            }
            ans++;
            grid[i][j] = 0;
            for (int k = 0; k < 4; k++)
            {
                q.push({ i + dx[k],j + dy[k] });
            }
        }
        return ans;
    }
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int ans = 0;
        for (int i = 0; i < grid.size(); i++)
        {
            for (int j = 0; j < grid[0].size(); j++)
            {
                // ans=max(ans,dfs(grid,i,j));
                ans = max(ans, bfs(grid, i, j));
            }
        }

        return ans;
    }

};

int main()
{
    Solution S;

    return 0;
}